class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];// 表示 i 为开始，j 为结束的回文串的长度
        int maxLen = 0;
        int x = 0;
        int y = 0;
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                char start = s.charAt(i);
                char end = s.charAt(j);
                if(start == end){
                    if(i == j) dp[i][j] = 1;
                    else if(i + 1 == j) dp[i][j] = 2;
                    else {
                        if(dp[i + 1][j - 1] > 0) dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }
                if(maxLen < dp[i][j]){
                    maxLen = dp[i][j];
                    x = i;
                    y = j;
                }
            }
        }
        return s.substring(x, y + 1);
    }
}